Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
Constraints:
The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100
My Solution
We can solve this with a helper function that does a preorder traversal of two trees simultaneously. In the helper, if both nodes are null, we return true. If one of the nodes is not null but the other is, we return false. If the two nodes have different values, we return false. Then if the left subtree of one node and right subtree of the other node are not the same, we return false. We then check whether the right subtree of one node is the same is the left subtree of the other node. If it passes all these checks, we return true. To initiate the comparison we just call the helper with the left and right subtrees of the input tree.
Time complexity would be O(n), where n is the size of the tree. Space complexity would be O(1) since we require only constant extra space.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return helper(root.left, root.right);
}
public boolean helper(TreeNode n1, TreeNode n2) {
if (n1 == null && n2 == null) {
return true;
}
if (!(n1 != null && n2 != null)) {
return false;
}
if (n1.val != n2.val) {
return false;
}
if (!helper(n1.left, n2.right)) {
return false;
}
return helper(n1.right, n2.left);
}
}